package arithmetic.LeetCode;

import java.util.Arrays;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 示例:
 *
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 说明:
 *
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 *
 *
 * https://leetcode-cn.com/problems/move-zeroes/
 * @author jiangfeng 2021/1/24 22:00
 */
public class MoveZero {
    public static void main(String[] args) {
        int[] a = new int[]{23,0,0,54,24,3,6,7};
        int[] a1 = new int[]{0,1,0,3,12};
        //System.out.println(Arrays.toString(maPao(a)));
        //System.out.println(Arrays.toString(xuanZe(a)));
        System.out.println(Arrays.toString(moveZero3(a1)));


    }

    public static int[] moveZero(int[] a) {
        int zoreIndex = 0;
        for (int i = 0; i < a.length-zoreIndex; i++) {
            if(a[i]==0){
                zoreIndex++;
                for (int j = i; j < a.length-zoreIndex; j++) {
                    swap(a,j,j+1);
                }
                i--;
            }
        }
        return a;
    }

    /**
     * 双指针法
     * @param nums
     * @return
     */
    public static int[] moveZero2(int[] nums) {
        // j表示下一个不为0的位置
        int j =0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[j++]=nums[i];
            }
        }
        // 把结尾都赋为0
        for (int i = j; i<nums.length; i++) {
            nums[i]=0;
        }
        return nums;
    }

    /**
     * 双指针 一次循环
     * @param nums
     * @return
     */
    public static int[] moveZero3(int[] nums) {
        // j表示下一个不为0的位置
        int j =0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                nums[j]=nums[i];
                // 不相等时一定是发现了0，把0向后移动
                if(i!=j){
                    nums[i]=0;
                }
                j++;
            }
        }

        return nums;
    }




    public static int[] maPao(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i+1; j < a.length; j++) {
                if(a[i]>a[j]){
                    swap(a,i,j);
                }
            }
        }
        return a;
    }

    public static int[] xuanZe(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if(a[j]>a[j+1]){
                    swap(a,j+1,j);
                }
            }
        }
        return a;
    }

    public static void swap(int[] a,int i,int j) {
       int temp =a[i];
       a[i] = a[j];
       a[j] = temp;
        System.out.println(Arrays.toString(a));
    }
}
